package com.cty._03_SolutionSeekingMindset._32_01_PrintTreeFromTopToBottom;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * @Auther: cty
 * @Date: 2020/7/11 11:40
 * @Description: 面试题32（一）：不分行从上往下打印二叉树
 * 题目：从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。
 * @version: 1.0
 */
public class PrintTreeFromTopToBottom {
    /**
     * 队列实现
     * @param treeRoot
     */
    public static void printTree(BinaryTreeNode treeRoot){
        if(treeRoot == null)
            return;

        Queue<BinaryTreeNode> queue = new ArrayDeque<>();
        queue.add(treeRoot);

        while(!queue.isEmpty()){
            BinaryTreeNode temp = queue.remove();
            System.out.print(temp.value + " ");

            if(temp.leftChild != null)
                queue.add(temp.leftChild);
            if(temp.rightChild != null)
                queue.add(temp.rightChild);
        }  // end while
        System.out.println();
    }  // end printTree()

    /**
     * 两个栈实现
     * @param treeRoot
     */
    public static void printTree02(BinaryTreeNode treeRoot){
        if(treeRoot == null)
            return;

        Stack<BinaryTreeNode> globalStack = new Stack<>();
        globalStack.push(treeRoot);
        boolean isRowEmpty = false;

        while(!isRowEmpty){
            isRowEmpty = true;
            Stack<BinaryTreeNode> localStack = new Stack<>();

            while(!globalStack.isEmpty()){
                BinaryTreeNode temp = globalStack.pop();
                System.out.print(temp.value + " ");

                if(temp.leftChild != null){
                    localStack.push(temp.leftChild);
                    isRowEmpty = false;
                }
                if(temp.rightChild != null){
                    localStack.push(temp.rightChild);
                    isRowEmpty = false;
                }
            }
            while(!localStack.isEmpty())
                globalStack.push(localStack.pop());

        }  // end while()

        System.out.println();
    }  // end printTree()

}  // end class

class BinaryTreeNode{
    int value;
    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;

    public BinaryTreeNode(){}

    public BinaryTreeNode(int value){this.value = value;}

}  // end class
